package com.AStarExample
{
	public class AStar
	{
		private var _startNode:Node;//开始点
		private var _endNode:Node;//结束点
		private var _grid:Grid;//网格
		private var _openArr:Array;//待查列表
		private var _closeArr:Array;//已查列表
		private var _path:Array;//寻路数组
		private var _heuristic:Function = diagonal;//启发函数   
		private var _straightCost:Number = 1.0;   //对称代价
		private var _diagCost:Number = Math.SQRT2; //对角代价
		public function AStar()
		{
			
		}
		
		public function findPath(grid:Grid):Boolean
		{
			this._grid = grid;
			this._closeArr = [];
			this._openArr = [];
			this._path = [];
			this._startNode = this._grid.startNode;
			this._endNode = this._grid.endNode;
			this._startNode.g = 0;
			this._startNode.h = this._heuristic(this._startNode);
			this._startNode.f = this._startNode.g + this._startNode.h;
			return search();
		}
		
		/**search 实际的查找函数**/
		private function search():Boolean
		{
			var node:Node = this._startNode;
			while(node != this._endNode)
			{
				var startCol:int = Math.max(0,node.y-1);
				var startRow:int = Math.max(0,node.x - 1);
				
				var endCol:int = Math.min(this._grid.colNum - 1,node.y+1);
				var endRow:int = Math.min(this._grid.rowNum - 1,node.x+1);
				var test:Node;
				for(var i:int = startRow;i<=endRow;i++)
				{
					for(var j:int = startCol;j<=endCol;j++)
					{
						test = this._grid.getNode(i,j) as Node;
						if(test == node || !test.walkable || !(this._grid.getNode(node.x,test.y).walkable)||!(this._grid.getNode(test.x,node.y).walkable))
						{
							continue;
						}
						
						var cost:Number = this._straightCost;
						if(node.x !=test.x && node.y!= test.y)
						{
							cost = this._diagCost;
						}
						
						var g:Number = node.g + cost;
						var h:Number = this._heuristic(test);
						var f:Number = g+h;
						if(isOpen(test)||isClose(test))
						{
							if(test.f>f)
							{
								test.f = f;
								test.g = g;
								test.h = h;
								test.parent = node;
							}
						}else
						{
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
							this._openArr.push(test);
						}
					}
				}
				
				this._closeArr.push(node);
				if(this._openArr.length == 0)
				{
					trace("无路可走");
					return false;
				}
				
				this._openArr.sortOn("f", Array.NUMERIC);   
				node = this._openArr.shift() as Node;   
			}
			this.buildPath();
			return true;
		}
		
		private function buildPath():void
		{
			var node:Node = this._endNode;
			this._path.push(node);
			while(node.parent &&node.parent != this._startNode)
			{
				node = node.parent;
				this._path.unshift(node);
			}
		}
		
		
		private function isOpen(node:Node):Boolean
		{
			for(var i:int = 0;i<this._openArr.length;i++)
			{
				var node1:Node = this._openArr[i];
				if(node1 == node)return true;
			}
			return false
		}
		
		private function isClose(node:Node):Boolean
		{
			for(var i:int = 0;i<this._closeArr.length;i++)
			{
				var node1:Node = this._closeArr[i];
				if(node1 == node)return true;
			}
			return false
		}
		
		/**对角启发函数**/
		private function diagonal(node:Node):Number  
		{  
			var dx:Number = Math.abs(node.x - _endNode.x);   
			var dy:Number = Math.abs(node.y - _endNode.y);   
			var diag:Number = Math.min(dx, dy);   
			var straight:Number = dx + dy;   
			return _diagCost * diag  + _straightCost * (straight - 2 * diag);   
		}
		
		public function getPath():Array
		{
			return this._path as Array;
		}
	}
}